package cn.demoncat.util.lang;

import cn.demoncat.util.lang.constant.StringConstant;
import cn.demoncat.util.lang.entity.CommonComparator;
import cn.demoncat.util.lang.fn.ArrBatchHandler;
import org.apache.commons.lang3.ArrayUtils;
import org.apache.commons.lang3.StringUtils;

import java.lang.reflect.Array;
import java.util.*;
import java.util.function.Function;
import java.util.function.Predicate;

/**
 * 数组的工具类
 * 
 * @author 延晓磊
 *
 * @since 2019年8月16日
 */
public class ArrayUtil {


	/**
	 * 判断是否为数组
	 * 
	 * @param o
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2019年10月10日
	 */
	public static boolean isArray(Object o) {
		return o.getClass().isArray();
	}

	/**
	 * 判断是否为数组
	 * 
	 * @param clazz
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2019年10月10日
	 */
	public static boolean isArray(Class<?> clazz) {
		return clazz.isArray();
	}

	/**
	 * toString
	 *
	 * @param arr
	 * @return
	 *
	 * @author 延晓磊
	 *
	 * @since 2020年6月28日
	 */
	public static <E>String toString(E[] arr) {
		if (arr == null || arr.length == 0) {
			return StringConstant.EMPTY_LIST;
		}
		// [1, 2, 3]
		StringBuilder str = new StringBuilder("[");
		int max = arr.length - 1;
		for (int i = 0; i < arr.length; i++) {
			str.append(arr[i]);
			if (i == max) {
				str.append("]");
			}else {
				str.append(", ");
			}
		}
		return str.toString();
	}

	/**
	 * toString
	 *
	 * @param arr
	 * @return
	 *
	 * @author 延晓磊
	 *
	 * @since 2020年6月28日
	 */
	public static String objToString(Object arr) {
		if (arr == null) {
			return StringConstant.EMPTY_LIST;
		}
		if (arr instanceof long[]) {
			return Arrays.toString((long[]) arr);
		} else if (arr instanceof int[]) {
			return Arrays.toString((int[]) arr);
		} else if (arr instanceof short[]) {
			return Arrays.toString((short[]) arr);
		} else if (arr instanceof char[]) {
			return Arrays.toString((char[]) arr);
		} else if (arr instanceof byte[]) {
			return Arrays.toString((byte[]) arr);
		} else if (arr instanceof boolean[]) {
			return Arrays.toString((boolean[]) arr);
		} else if (arr instanceof float[]) {
			return Arrays.toString((float[]) arr);
		} else if (arr instanceof double[]) {
			return Arrays.toString((double[]) arr);
		} else{
			return Arrays.deepToString((Object[]) arr);
		}
	}

	/**
	 * 获取数组元素的类型
	 * 
	 * @param arr
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2019年8月27日
	 */
	public static <T> Class<?> getType(T[] arr) {
		return arr.getClass().getComponentType();
	}

	/**
	 * 是否包含null
	 *
	 * @param arr	数组，必须非空
	 * @return
	 */
	@SafeVarargs
	public static <T> boolean hasNull(T... arr) {
		for (T e : arr) {
			if (null == e) {
				return true;
			}
		}
		return false;
	}

	/**
	 * 是否都为null
	 *
	 * @param arr	数组，必须非空
	 * @return
	 */
	@SafeVarargs
	public static <T> boolean isAllNull(T... arr) {
		for (T e : arr) {
		    if (null != e) {
		    	return false;
		    }
		}
		return false;
	}

	/**
	 * 首个非null
	 *
	 * @param arr	数组，必须非空
	 * @return
	 */
	@SafeVarargs
	public static <T> T firstNonNull(T... arr) {
		for (T e : arr) {
			if (null != e) {
				return e;
			}
		}
		return null;
	}

	/**
	 * 新建数组
	 * 
	 * @param clazz	元素类型
	 * @param size	长度
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月14日
	 */
	@SuppressWarnings("unchecked")
	public static <T>T[] instance(Class<?> clazz, int size){
		return (T[]) Array.newInstance(clazz, size);
	}
	
	/**
	 * 新建二维数组
	 * 
	 * @param clazz	元素类型
	 * @param size1	长度
	 * @param size2	长度
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月14日
	 */
	@SuppressWarnings("unchecked")
	public static <T>T[][] instance2(Class<?> clazz, int size1, int size2){
		return (T[][]) Array.newInstance(clazz, size1, size2);
	}

	/**
	 * 填充
	 *
	 * @param arr
	 * @param val	填充值
	 * @param <T>
	 * @return
	 *
	 * @author 延晓磊
	 *
	 * @since 2020年7月14日
	 */
	public static <T>T[] fill(T[] arr, T val){
		Arrays.fill(arr, val);
		return arr;
	}

	/**
	 * 创建数组
	 * 
	 * @param arr 数组元素
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2019年8月27日
	 */
	@SafeVarargs
	public static <T> T[] toArray(T... arr) {
		return arr;
	}

	/**
	 * 转换为字符串数组
	 *
	 * @param arr
	 * @return
	 *
	 * @author 延晓磊
	 *
	 * @since 2019年8月27日
	 */
	public static String[] toStrArray(Object[] arr){
		String[] s = new String[arr.length];
		for (int i = 0; i < arr.length; i++) {
			s[i] = StringUtil.toString(arr[i]);
		}
		return s;
	}

	/**
	 * 转换为Object数组
	 *
	 * @param arr
	 * @return
	 *
	 * @author 延晓磊
	 *
	 * @since 2019年8月27日
	 */
	public static Object[] toObjArray(Object[] arr){
		return arr;
	}

	/**
	 * 获取数组的可更改List
	 * 注意：Arrays.asList获取的只是数组的只读视图，所以要再创建列表
	 * 
	 * @param arr 数组
	 * @return	转换后的集合，可以对集合进行增删改
	 */
	public static <T> List<T> toList(T[] arr) {
		return CollectionUtil.arrayToList(arr);
	}

	/**
	 * 获取数组的可更改Set
	 * 
	 * @param arr 数组
	 * @return	转换后的集合，可以对集合进行增删改
	 */
	public static <T> Set<T> toSet(T[] arr) {
		return CollectionUtil.arrayToSet(arr);
	}

	/**
	 * 转换String[]为List<Long>
	 * 
	 * @param arr
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2019年8月16日
	 */
	public static List<Long> toLongList(String[] arr) {
		if (arr == null) {
			return null;
		}
		List<Long> list = new ArrayList<>(arr.length);
		for (String id : arr) {
			list.add(LongUtil.valueOf(id));
		}
		return list;
	}

	/**
	 * 转换String[]为List<Integer>
	 * 
	 * @param arr
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2019年8月16日
	 */
	public static List<Integer> toIntList(String[] arr) {
		if (arr == null) {
			return null;
		}
		List<Integer> list = new ArrayList<>(arr.length);
		for (String id : arr) {
			list.add(IntegerUtil.valueOf(id));
		}
		return list;
	}

	/**
	 * 转换String[]为Set<Long>
	 * 
	 * @param arr
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2019年8月16日
	 */
	public static Set<Long> toLongSet(String[] arr) {
		if (arr == null) {
			return null;
		}
		Set<Long> list = new HashSet<>(arr.length);
		for (String id : arr) {
			list.add(LongUtil.valueOf(id));
		}
		return list;
	}

	/**
	 * 转换String[]为Set<Integer>
	 * 
	 * @param arr
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2019年8月16日
	 */
	public static Set<Integer> toIntSet(String[] arr) {
		if (arr == null) {
			return null;
		}
		Set<Integer> list = new HashSet<>(arr.length);
		for (String id : arr) {
			list.add(IntegerUtil.valueOf(id));
		}
		return list;
	}

	/**
	 * 去除空元素
	 * 
	 * @param arr
	 * @return 
	 * 
	 * @author 延晓磊
	 *
	 * @since 2019年8月16日
	 */
	public static String[] trimStr(String[] arr) {
		if (arr == null) {
			return null;
		}
		if (arr.length == 0) {
			return arr;
		}
		List<String> list = new ArrayList<>(arr.length);
		for (String el : arr) {
			if (StringUtils.isNotBlank(el)) {
				list.add(el);
			}
		}
		return CollectionUtil.toStrArray(list);
	}

	/**
	 * 去除空元素，去重
	 * 
	 * @param arr
	 * @return 
	 * 
	 * @author 延晓磊
	 *
	 * @since 2019年8月16日
	 */
	public static String[] trimStrUnique(String[] arr) {
		if (arr == null) {
			return null;
		}
		if (arr.length == 0) {
			return arr;
		}
		Set<String> list = new HashSet<>(arr.length);
		for (String el : arr) {
			if (StringUtils.isNotBlank(el)) {
				list.add(el);
			}
		}
		return CollectionUtil.toStrArray(list);
	}

	/**
	 * 去除空元素
	 * 
	 * @param arr
	 * @return 
	 * 
	 * @author 延晓磊
	 *
	 * @since 2019年8月16日
	 */
	public static Integer[] trimInt(Integer[] arr) {
		if (arr == null) {
			return null;
		}
		if (arr.length == 0) {
			return arr;
		}
		List<Integer> list = new ArrayList<>(arr.length);
		for (Integer el : arr) {
			if (el != null) {
				list.add(el);
			}
		}
		return CollectionUtil.toIntArray(list);
	}

	/**
	 * 去除空元素，去重
	 * 
	 * @param arr
	 * @return 
	 * 
	 * @author 延晓磊
	 *
	 * @since 2019年8月16日
	 */
	public static Integer[] trimIntUnique(Integer[] arr) {
		if (arr == null) {
			return null;
		}
		if (arr.length == 0) {
			return arr;
		}
		Set<Integer> list = new HashSet<>(arr.length);
		for (Integer el : arr) {
			if (el != null) {
				list.add(el);
			}
		}
		return CollectionUtil.toIntArray(list);
	}

	/**
	 * 去除空元素
	 * 
	 * @param arr
	 * @return 
	 * 
	 * @author 延晓磊
	 *
	 * @since 2019年8月16日
	 */
	public static Long[] trimLong(Long[] arr) {
		if (arr == null) {
			return null;
		}
		if (arr.length == 0) {
			return arr;
		}
		List<Long> list = new ArrayList<>(arr.length);
		for (Long el : arr) {
			if (el != null) {
				list.add(el);
			}
		}
		return CollectionUtil.toLongArray(list);
	}

	/**
	 * 去除空元素，去重
	 * 
	 * @param arr
	 * @return 
	 * 
	 * @author 延晓磊
	 *
	 * @since 2019年8月16日
	 */
	public static Long[] trimLongUnique(Long[] arr) {
		if (arr == null) {
			return null;
		}
		if (arr.length == 0) {
			return arr;
		}
		Set<Long> list = new HashSet<>(arr.length);
		for (Long el : arr) {
			if (el != null) {
				list.add(el);
			}
		}
		return CollectionUtil.toLongArray(list);
	}

	/**
	 * 去除空元素
	 * 
	 * @param arr
	 * @return 只读arr
	 * 
	 * @author 延晓磊
	 *
	 * @since 2019年8月16日
	 */
	public static <T> T[] trim(T[] arr) {
		if (arr == null) {
			return null;
		}
		if (arr.length == 0) {
			return arr;
		}
		List<T> list = new ArrayList<>(arr.length);
		for (T el : arr) {
			if (el != null) {
				list.add(el);
			}
		}
		return list.toArray(arr);
	}

	/**
	 * 去除空元素，去重
	 * 
	 * @param arr
	 * @return 只读arr
	 * 
	 * @author 延晓磊
	 *
	 * @since 2019年8月16日
	 */
	public static <T> T[] trimUnique(T[] arr) {
		if (arr == null) {
			return null;
		}
		if (arr.length == 0) {
			return arr;
		}
		Set<T> list = new HashSet<>(arr.length);
		for (T el : arr) {
			if (el != null) {
				list.add(el);
			}
		}
		return list.toArray(arr);
	}

	/**
	 * 将多个同类型数组合并为一个数组
	 * 
	 * @param  arrs 多个同类型数组，或者二维数组
	 * @return 合并后的数组
	 */
	@SafeVarargs
	public static <T> T[] merge(T[]... arrs) {
		// 空参
		if (ArrayUtils.isEmpty(arrs)) {
			return null;
		}
		// 添加到list
		List<T> list = new ArrayList<>();
		T[] typeArray = null;
		for (T[] arr : arrs) {
			if (ArrayUtils.isNotEmpty(arr)) {
				if (typeArray == null) {
					typeArray = arr;
				}
				Collections.addAll(list, arr);
			}
		}
		// 转换为数组
		if (!list.isEmpty()) {
			return list.toArray(typeArray);
		}
		return null;
	}

	/**
	 * 安全获取数组元素
	 * 
	 * @param arr
	 * @param index		0首个，-1末个
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2019年1月23日
	 */
	public static <T> T get(T[] arr, int index) {
		// 非空
		if (null == arr || arr.length == 0) {
			return null;
		}
		// 倒数
		if (index < 0) {
			index = arr.length + index;
			if (index < 0) {
				return null;
			}
		}
		// 超限
		if (index > arr.length -1) {
			return null;
		}
		return arr[index];
	}
 

	/**
	 * 安全获取数组元素
	 * 
	 * @param arr
	 * @param i		1维索引
	 * @param j		2维索引
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2019年1月23日
	 */
	public static <T> T get(T[][] arr, int i, int j) {
		// 获取1维
		T[] ts = get(arr, i);
		if (ts == null) {
			return null;
		}
		// 获取2维
		return get(ts, j);
	}

	/**
	 * 查找元素
	 *
	 * @param arr		列表
	 * @param predicate	条件
	 * @return 首个满足条件的元素
	 *
	 * @author 延晓磊
	 *
	 * @since 2016年6月10日
	 */
	public static <E> E get(E[] arr, Predicate<? super E> predicate) {
		if (ArrayUtils.isEmpty(arr) || predicate == null) {
			return null;
		}
		for (E e : arr) {
			if (predicate.test(e)) {
				return e;
			}
		}
		return null;
	}

	/**
	 * 分批处理数据
	 * 
	 * @param arr	数组
	 * @param step	分批数
	 * @param handler	处理器：停止分批处理时返回非null，继续处理返回null
	 * 
	 * @author 延晓磊
	 *
	 * @since 2019年8月22日
	 */
	public static <T, R> R batchs(T[] arr, int step, ArrBatchHandler<T, R> handler) {
		// 迭代次数
		int times = arr.length % step == 0 ? arr.length / step : arr.length / step + 1;
		R r = null;
		for (int i = 0; i < times; i++) {
			// 分批处理
			if (i == times - 1) {
				r = handler.callback(ArrayUtils.subarray(arr, i * step, arr.length));
			} else {
				r = handler.callback(ArrayUtils.subarray(arr, i * step, (i + 1) * step));
			}
			// 返回非null时终止批处理
			if (r != null) {
				return r;
			}
		}
		return r;
	}

	/**
	 * 二维数组，转换为稀疏数组
	 * 
	 * @param arr 二维数组：保存大量的无用数据（默认值 0）
	 * 
	 * @return 稀疏数组：只保存有效数据及其位置，实现数据压缩
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月23日
	 */
	public static int[][] toSparse(int[][] arr){
		// 获取有效数据个数
		int sum = 0;
		for (int[] arr2 : arr) {
			for (int data : arr2) {
				// 有效数据（非默认值）
				if (data != 0) {
					sum ++;
				}
			}
		}
		// 创建稀疏数组：T[sum+1][3]
		int[][] sparse = new int[sum+1][3];
		// 保存头信息：行数，列数，有效数据个数
		sparse[0][0] = arr.length;
		sparse[0][1] = arr[0].length;
		sparse[0][2] = sum;
		// 保存有效数据：行索引，列索引，数据
		int index = 0;
		int data;
		for (int i = 0; i < sparse[0][0]; i++) {
			for (int j = 0; j < sparse[0][1]; j++) {
				// 有效数据（非默认值）
				data = arr[i][j];
				if (data != 0) {
					index ++;
					sparse[index][0] = i;
					sparse[index][1] = j;
					sparse[index][2] = data;
				}
			}
		}
		return sparse;
	}
	
	/**
	 * 稀疏数组，解析为二维数组
	 * 
	 * @param sparse 稀疏数组（压缩数据）
	 * 
	 * @return 二维数组（原始数据）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月23日
	 */
	public static int[][] parseSparse(int[][] sparse){
		// 创建原始数组：行数，列数
		int[][] arr = new int[sparse[0][0]][sparse[0][1]];
		// 赋值有效数据：行索引，列索引，数据
		for (int i = 1; i < sparse.length; i++) {
			arr[sparse[i][0]][sparse[i][1]] = sparse[i][2];
		}
		return arr;
	}
	
	/**
	 * 判断两个单元格是否在同一条线上
	 * 
	 * @param row1	行索引
	 * @param row2
	 * @param col1	列索引
	 * @param col2
	 * 
	 * @return true直线/斜线
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月1日
	 */
	public static boolean isOnLine(int row1, int row2, int col1, int col2) {
		// 同行，同列，斜线
		return row1 == row2 || col1 == col2 || Math.abs(row1 - row2) == Math.abs(col1 - col2);
	}
	
	/**
	 * 冒泡排序：O(n^2)
	 * 
	 * @param arr	数组
	 * @param comparator	比较器
	 * 
	 * @return 排序后的数组
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月3日
	 */
	public static <E>E[] bubbleSort(E[] arr, Comparator<E> comparator){
		if (arr == null || arr.length < 2) {
			return arr;
		}
		// 冒泡排序：依次比较相邻元素，如果逆序则交换
		boolean flag = true;
		E curr;
		E next;
		for (int i = 1; i < arr.length; i++) {
			for (int j = 0; j < arr.length -i; j++) {
				curr = arr[j];
				next = arr[j+1];
				// 比较相邻元素，逆序则交换
				if (comparator.compare(curr, next) > 0) {
					flag = false;
					arr[j] = next;
					arr[j+1] = curr;
				}
			}
			// 数组有序（未交换元素）
			if (flag) {
				break;
			}else {
				// 重置flag，进入下一轮比较
				flag = true;
			}
		}
		return arr;
	}
	
	/**
	 * 冒泡排序：O(n^2)
	 * 
	 * @param arr	数组
	 * 
	 * @return 排序后的数组
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月3日
	 */
	public static <E extends Comparable<E>>E[] bubbleSort(E[] arr){
		return bubbleSort(arr, CommonComparator.get());
	}
	
	/**
	 * 选择排序：O(n^2)
	 * 
	 * @param arr	数组
	 * @param comparator	比较器
	 * 
	 * @return 排序后的数组
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月3日
	 */
	public static <E>E[] selectSort(E[] arr, Comparator<E> comparator){
		if (arr == null || arr.length < 2) {
			return arr;
		}
		// 选择排序：依次比较所有元素，选择最小元素，与当前元素交换
		E min;
		int minI;
		for (int i = 0; i < arr.length -1; i++) {
			// 假设当前元素为最小元素
			min = arr[i];
			minI = i;
			// 依次比较其它元素
			for (int j = i + 1; j < arr.length; j++) {
				if (comparator.compare(min, arr[j]) > 0) {
					// 重置最小元素
					min = arr[j];
					minI = j;
				}
			}
			// 交换当前元素和最小元素
			if (i != minI) {
				arr[minI] = arr[i];
				arr[i] = min;
			}
		}
		return arr;
	}
	
	/**
	 * 选择排序：O(n^2)
	 * 
	 * @param arr	数组
	 * 
	 * @return 排序后的数组
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月3日
	 */
	public static <E extends Comparable<E>>E[] selectSort(E[] arr){
		return selectSort(arr, CommonComparator.get());
	}
	
	/**
	 * 插入排序：O(n^2)
	 * 
	 * @param arr	数组
	 * @param comparator	比较器
	 * 
	 * @return 排序后的数组
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月3日
	 */
	public static <E>E[] insertSort(E[] arr, Comparator<E> comparator){
		if (arr == null || arr.length < 2) {
			return arr;
		}
		// 插入排序：将数组分割为有序区（首个元素）和无序区（其它元素），然后依次将无序区的元素插入到有序区的适当位置
		E curr;
		int index;
		for (int i = 1; i < arr.length; i++) {
			// 无序区的当前元素
			curr = arr[i];
			// 有序区的末元素索引
			index = i - 1; 
			// 与有序区元素比较，如果有序区元素大则继续向前比较
			while (index >= 0 && comparator.compare(arr[index], curr) > 0) {
				// 有序区元素大于当前元素：后移，方便当前元素插入/前面的元素后移
				arr[index+1] = arr[index];
				// 继续向前比较
				index--;
			}
			// 当前元素在有序区的适当位置
			index = index + 1;
			// 有序区元素大于当前元素，向前插入；反之，添加在末尾
			if (i > index) {
				// 向前插入
				arr[index] = curr;
			}
		}
		return arr;
	}
	
	/**
	 * 插入排序：O(n^2)
	 * 
	 * @param arr	数组
	 * 
	 * @return 排序后的数组
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月3日
	 */
	public static <E extends Comparable<E>>E[] insertSort(E[] arr){
		return insertSort(arr, CommonComparator.get());
	}
	
	/**
	 * 希尔排序：O(n^(1.3~2))
	 * 
	 * @param arr	数组
	 * @param comparator	比较器
	 * 
	 * @return 排序后的数组
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月3日
	 */
	public static <E>E[] shellSort(E[] arr, Comparator<E> comparator){
		if (arr == null || arr.length < 2) {
			return arr;
		}
		// 希尔排序：增量分组，然后对每组元素插入排序，当增量递减至1（只有1个分组）时，完成整体排序
		E curr;
		int index;
		// 增量 == 分组数量 == 组内元素间隔 == 开始为n/2，以?/2递减
		for (int gap = arr.length/2; gap > 0; gap /= 2) {
			// 组内插入排序：将每个组分割为有序区（首个元素）和无序区（其它元素），然后轮流对每个组插入排序
			for (int i = gap; i < arr.length; i++) {
				// 无序区的当前元素（归属分组1,2,3...）
				curr = arr[i];
				// 有序区的末元素索引（当前元素按增量间隔回退，即组内上一个元素）
				index = i - gap; 
				// 与有序区元素比较，如果有序区元素大则继续向前比较
				while (index >= 0 && comparator.compare(arr[index], curr) > 0) {
					// 有序区元素大于当前元素：后移，方便当前元素插入/前面的元素后移
					arr[index+gap] = arr[index];
					// 继续向前比较
					index -= gap;
				}
				// 当前元素在有序区的适当位置
				index = index + gap;
				// 有序区元素大于当前元素，向前插入；反之，添加在末尾
				if (i > index) {
					// 向前插入
					arr[index] = curr;
				}
			}
		}
		return arr;
	}
	
	/**
	 * 希尔排序：O(n^(1.3~2))
	 * 
	 * @param arr	数组
	 * 
	 * @return 排序后的数组
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月3日
	 */
	public static <E extends Comparable<E>>E[] shellSort(E[] arr){
		return shellSort(arr, CommonComparator.get());
	}

	/**
	 * 快速排序：O(n*log2n) ~ O(n^2)
	 * 
	 * @param arr			数组
	 * @param comparator	比较器
	 * 
	 * @return 排序后的数组
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月11日
	 */
	public static <E>E[] quickSort(E[] arr, Comparator<E> comparator) {
		if (arr == null || arr.length < 2) {
			return arr;
		}
		// 快速排序：使用分治法，以中间元素为基准，将数组递归分割、交换
		return quickSort(arr, comparator, 0, arr.length -1);
	}
	
	/**
	 * 快速排序：O(n*log2n) ~ O(n^2)
	 * 
	 * @param arr			数组
	 * 
	 * @return 排序后的数组
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月11日
	 */
	public static <E extends Comparable<E>>E[] quickSort(E[] arr){
		return quickSort(arr, CommonComparator.get());
	}
	
	/**
	 * 快速排序：O(n*log2n) ~ O(n^2)
	 * 
	 * @param arr			数组
	 * @param comparator	比较器
	 * @param left			左指针，初始为0
	 * @param right			右指针，初始为末索引
	 * 
	 * @return 排序后的数组
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月11日
	 */
	private static <E>E[] quickSort(E[] arr, Comparator<E> comparator, int left, int right) {
		// 临时指针
		int l = left;
		int r = right;
		// 基准元素(中分)
		E pivot = arr[(left + right) / 2];
		// 交换变量
		E temp;
		// 分割数组：将左侧大于pivot的元素移到右侧，将右侧小于pivot的元素移到左侧，直到指针重合（比较完成）
		while(l < r) { 
			// left向右遍历，找出大于pivot的元素
			while(comparator.compare(arr[l], pivot) < 0) {
				l ++;
			}
			// right向左遍历，找出小于pivot的元素
			while(comparator.compare(arr[r], pivot) > 0) {
				r --;
			}
			// 未找到需要移动的元素
			if( l >= r) {
				break;
			}
			// 交换
			temp = arr[l];
			arr[l] = arr[r];
			arr[r] = temp;
			// 如果pivot参与交换，直接推进指针（不需要重复比较）
			if(arr[l] == pivot) {
				r --;
			}
			if(arr[r] == pivot) {
				l ++;
			}
		}
		// 指针重合的位置，元素排序确定，可以直接排除比较
		if (l == r) {
			r --;
			l ++;
		}
		// 局部排序（递归，直至无法分割）
		if(left < r) {
			quickSort(arr, comparator, left, r);
		}
		if(right > l) {
			quickSort(arr, comparator, l, right);
		}
		return arr;
	}
	 
	/**
	 * 归并排序：O(nlog2n)
	 * 
	 * @param arr			数组
	 * @param comparator	比较器
	 * 
	 * @return 排序后的数组
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月14日
	 */
	public static <E>E[] mergeSort(E[] arr, Comparator<E> comparator) {
		if (arr == null || arr.length < 2) {
			return arr;
		}
		// 归并排序：使用分治法，将数组递归分割、排序、合并
		return mergeSort(arr, 0, arr.length -1, instance(getType(arr), arr.length), comparator);
	}
	
	/**
	 * 归并排序：O(nlog2n)
	 * 
	 * @param arr	数组
	 * 
	 * @return 排序后的数组
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月14日
	 */
	public static <E extends Comparable<E>>E[] mergeSort(E[] arr) {
		return mergeSort(arr, CommonComparator.get());
	}
	
	/**
	 * 归并排序：O(nlog2n)
	 * 
	 * @param arr	原始数组
	 * @param left	左索引，初始为0
	 * @param right	右索引，初始为末索引
	 * @param temp	中转数组
	 * @param comparator	比较器
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月14日
	 */
	private static <E>E[] mergeSort(E[] arr, int left, int right, E[] temp, Comparator<E> comparator) {
		if(left < right) {
			// 分解
			int mid = (left + right) / 2;
			// - 递归左部分
			mergeSort(arr, left, mid, temp, comparator);
			// - 递归右部分
			mergeSort(arr, mid + 1, right, temp, comparator);
			// 合并
			mergeSortMerge(arr, left, mid, right, temp, comparator);
		}
		return arr;
	}
	
	/**
	 * 归并排序 - 合并
	 * 
	 * @param arr	原始数组
	 * @param left	左索引
	 * @param mid	中索引
	 * @param right	右索引
	 * @param temp	中转数组
	 * @param comparator	比较器
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月14日
	 */
	private static <E>void mergeSortMerge(E[] arr, int left, int mid, int right, E[] temp, Comparator<E> comparator) {
		// 左数组的初始索引
		int i = left;
		// 右数组的初始索引
		int j = mid + 1; 
		// 中转数组的填充指针
		int t = 0;
		
		// 将左右数组的元素按大小依次加入中转数组，直到一侧数组存放完毕
		while (i <= mid && j <= right) {//继续
			// 比较左右数组的当前元素，较小者加入中转数组，递增指针
			if (comparator.compare(arr[i], arr[j]) <= 0) {
				temp[t] = arr[i];
				t ++;
				i ++;
			}else {
				temp[t] = arr[j];
				t ++;
				j ++;
			}
		}
		
		// 剩余元素直接加入中转数组，完成分批合并（局部有序）
		while(i <= mid) { 
			temp[t] = arr[i];
			t ++;
			i ++;	
		}
		while( j <= right) {
			temp[t] = arr[j];
			t ++;
			j ++;	
		}
		
		// 将合并后的中转数组拷贝回原数组（完成排序）
		i = left;
		t = 0;
		while(i <= right) { 
			arr[i] = temp[t];
			t ++;
			i ++;
		}
	}
	
	/**
	 * 基数排序：O(n*10)
	 * 
	 * @param arr
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static int[] radixSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return arr;
		}
		// 桶
		int[][] bucket = new int[10][arr.length];
		// 桶指针
		int[] bucketCount = new int[10];
		// 装桶次数（数据位数）
		int max = arr[0];
		for (int i = 1; i < arr.length; i++) {
			if (arr[i] > max) {
				max = arr[i];
			}
		}
		int times = (StringConstant.EMPTY + max).length();
		// 桶排序
		int index = 0;
		int digit = 1;
		int val;
		for (int i = 0; i < times; i++) {
			// 装桶
			for (int e : arr) {
				// 位值
				val = e / digit % 10;
				// 分配
				bucket[val][bucketCount[val]++] = e;
			}
			// 依次放回
			for (int j = 0; j < bucketCount.length; j++) {
				if (bucketCount[j] > 0) {
					for (int j2 = 0; j2 < bucketCount[j]; j2++) {
						arr[index++] = bucket[j][j2];
					}
					bucketCount[j] = 0;
				}
			}
			// 下一轮
			index = 0;
			digit *= 10;
		}
		return arr;
	}
	
	/**
	 * 堆排序：O(nlog2n)
	 * 
	 * @param arr			原数据
	 * @param comparator	比较器
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月19日
	 */
	public static <E>E[] heapSort(E[] arr, Comparator<E> comparator){
		if (arr == null || arr.length < 2) {
			return arr;
		}
		// 构建大顶堆
		for(int i = arr.length / 2 - 1; i >= 0; i--){
			// 从最后一个分枝结点开始，向上调整堆顶
			adjustHeap(arr, i, arr.length, comparator);
		}
		// 堆排序：通过堆的数据结构来确定最大值，每轮循环确定一个最大值，直到全部有序
		E tmp;
		for(int i = arr.length - 1; i > 0; i--){
			// 交换堆顶（将确定的最大值放在末尾，不再参与排序）
			tmp = arr[0];
			arr[0] = arr[i];
			arr[i] = tmp;
			// 重复处理剩余元素（找出最大元素放到堆顶，交换到末尾）
			adjustHeap(arr, 0, i, comparator);
		}
		return arr;
	}
	
	/**
	 * 堆排序：O(nlog2n)
	 * 
	 * @param arr			原数据
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月19日
	 */
	public static <E extends Comparable<E>>E[] heapSort(E[] arr){
		return heapSort(arr, CommonComparator.get());
	}
	
	/**
	 * 堆排序 - 调整大顶堆
	 * 
	 * @param arr		原始数组
	 * @param i			待调整的分枝结点（对该子树进行调整）
	 * @param length	元素个数（随着排序过程递减）
	 * @param comparator	比较器
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月19日
	 */
	private static <E>void adjustHeap(E[] arr, int i, int length, Comparator<E> comparator){
		// 当前结点
		E tmp = arr[i];
		// k = i.left
		for(int k= i * 2 + 1; k < length; k = k * 2 + 1){
			// 如果左结点小于右结点，k = i.right
			if(k + 1 < length && comparator.compare(arr[k], arr[k+1]) < 0){
				k++;
			}
			// 如果子结点大于结点，调整堆顶
			if(comparator.compare(arr[k], tmp) > 0){
				arr[i] = arr[k];
				// 循环比较，找出以i为根的树中的最大值
				i = k;
			}else{
				break;
			}
		}
		// 交换
		arr[i] = tmp;
	}
	
	/**
	 * 顺序（线性）查找
	 * 
	 * @param arr		数组（equals）
	 * @param target	目标
	 * 
	 * @return 第1个查找到的索引，-1表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static <E>int orderSearch(E[] arr, E target){
		// 数据校验
		if (arr == null || target == null || arr.length == 0) {
			return -1;
		}
		// 顺序查询：逐一遍历比对
		for (int i = 0; i < arr.length; i++) {
			if (target.equals(arr[i])) {
				// 找到相等元素
				return i;
			}
		}
		// 未找到
		return -1;
	}
	
	/**
	 * 顺序（线性）查找
	 * 
	 * @param arr		数组（equals）
	 * @param target	目标
	 * 
	 * @return 所在索引集（有序），空表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static <E>List<Integer> orderSearchs(E[] arr, E target){
		// 索引存储器
		List<Integer> indexs = new ArrayList<>();
		// 数据校验
		if (arr == null || target == null || arr.length == 0) {
			return indexs;
		}
		// 顺序查询：逐一遍历比对
		for (int i = 0; i < arr.length; i++) {
			if (target.equals(arr[i])) {
				// 找到相等元素
				indexs.add(i);
			}
		}
		return indexs;
	}
	
	/**
	 * 顺序（线性）查找
	 * 
	 * @param arr			数组（compare = equals）
	 * @param target		目标
	 * @param comparator	比较器
	 * 
	 * @return 第1个查找到的索引，-1表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static <E>int orderSearch(E[] arr, E target, Comparator<E> comparator){
		// 数据校验
		if (arr == null || target == null || arr.length == 0) {
			return -1;
		}
		// 顺序查询：逐一遍历比对
		for (int i = 0; i < arr.length; i++) {
			if (comparator.compare(target, arr[i]) == 0) {
				// 找到相等元素
				return i;
			}
		}
		// 未找到
		return -1;
	}
	
	/**
	 * 顺序（线性）查找
	 * 
	 * @param arr			数组（compare = equals）
	 * @param target		目标
	 * @param comparator	比较器
	 * 
	 * @return 所在索引集（有序），空表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static <E>List<Integer> orderSearchs(E[] arr, E target, Comparator<E> comparator){
		// 索引存储器
		List<Integer> indexs = new ArrayList<>();
		// 数据校验
		if (arr == null || target == null || arr.length == 0) {
			return indexs;
		}
		// 顺序查询：逐一遍历比对
		for (int i = 0; i < arr.length; i++) {
			if (comparator.compare(target, arr[i]) == 0) {
				// 找到相等元素
				indexs.add(i);
			}
		}
		return indexs;
	}
	
	/**
	 * 二分（折半）查找 - 循环
	 * 
	 * @param arr			有序数组（compare = equals）
	 * @param target		目标
	 * @param comparator	比较器
	 * 
	 * @return 第1个查找到的索引，-1表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static <E>int binarySearch(E[] arr, E target, Comparator<E> comparator){
		// 数据校验
		if (arr == null || target == null || arr.length == 0) {
			return -1;
		}
		// 二分查找：对有序数组，以n/2循环切分、查找
		int left = 0;
		int right = arr.length -1;
		int mid;
		int cp;
		while (left <= right) {
			// 折半切分
			mid = (left + right) /2;
			cp = comparator.compare(target, arr[mid]);
			if (cp < 0) {
				// 目标 < 中点
				right = mid -1;
			}else if (cp > 0) {
				// 中点 < 目标
				left = mid + 1;
			}else {
				return mid;
			}
		}
		// 未找到
		return -1;
	}
	
	/**
	 * 二分（折半）查找 - 循环
	 * 
	 * @param arr			有序数组（compare = equals）
	 * @param target		目标
	 * 
	 * @return 第1个查找到的索引，-1表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static <E extends Comparable<E>>int binarySearch(E[] arr, E target){
		return binarySearch(arr, target, CommonComparator.get());
	}
	
	/**
	 * 二分（折半）查找 - 循环
	 * 
	 * @param arr			有序数组（compare = equals）
	 * @param target		目标
	 * @param comparator	比较器
	 * 
	 * @return 所在索引集（无序），空表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static <E>List<Integer> binarySearchs(E[] arr, E target, Comparator<E> comparator){
		// 索引存储器
		List<Integer> indexs = new ArrayList<>();
		// 数据校验
		if (arr == null || target == null || arr.length == 0) {
			return indexs;
		}		
		// 二分查找：对有序数组，以n/2循环切分、查找
		int left = 0;
		int right = arr.length -1;
		int mid;
		int cp;
		while (left <= right) {
			// 折半切分
			mid = (left + right) /2;
			cp = comparator.compare(target, arr[mid]);
			if (cp < 0) {
				// 目标 < 中点
				right = mid -1;
			}else if (cp > 0) {
				// 中点 < 目标
				left = mid + 1;
			}else {
				// 目标 = 中点
				indexs.add(mid);
				// 扫描左侧
				right = mid;
				while (true) {
					right--;
					if (right < 0 || comparator.compare(target, arr[right]) != 0) {
						break;
					}
					indexs.add(right);
				}
				// 扫描右侧
				left = mid;
				right = arr.length - 1;
				while (true) {
					left++;
					if (left > right || comparator.compare(target, arr[left]) != 0) {
						break;
					}
					indexs.add(left);
				}
				return indexs;
			}
		}
		// 未找到
		return indexs;
	}
	
	/**
	 * 二分（折半）查找 - 循环
	 * 
	 * @param arr			有序数组（compare = equals）
	 * @param target		目标
	 * 
	 * @return 所在索引集（无序），空表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static <E extends Comparable<E>>List<Integer> binarySearchs(E[] arr, E target){
		return binarySearchs(arr, target, CommonComparator.get());
	}
	
	
	/**
	 * 二分（折半）查找 - 递归
	 * 
	 * @param arr			有序数组（compare = equals）
	 * @param target		目标
	 * @param comparator	比较器
	 * 
	 * @return 第1个查找到的索引，-1表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static <E>int binarySearch2(E[] arr, E target, Comparator<E> comparator){
		// 数据校验
		if (arr == null || target == null || arr.length == 0) {
			return -1;
		}
		// 二分查找：对有序数组，以n/2递归切分、查找
		return binarySearch2(arr, target, 0, arr.length - 1, comparator);
	}
	
	/**
	 * 二分（折半）查找 - 递归
	 * 
	 * @param arr			有序数组（compare = equals）
	 * @param target		目标
	 * 
	 * @return 第1个查找到的索引，-1表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static <E extends Comparable<E>>int binarySearch2(E[] arr, E target){
		return binarySearch2(arr, target, CommonComparator.get());
	}
	
	/**
	 * 二分（折半）查找 - 递归
	 * 
	 * @param arr			有序数组（compare = equals）
	 * @param target		目标
	 * @param comparator	比较器
	 * 
	 * @return 所在索引集（无序），空表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static <E>List<Integer> binarySearchs2(E[] arr, E target, Comparator<E> comparator){
		// 索引存储器
		List<Integer> indexs = new ArrayList<>();
		// 数据校验
		if (arr == null || target == null || arr.length == 0) {
			return indexs;
		}		
		// 二分查找：对有序数组，以n/2递归切分、查找
		return binarySearchs2(arr, target, 0, arr.length -1 , comparator, indexs);
	}
	
	/**
	 * 二分（折半）查找 - 递归
	 * 
	 * @param arr			有序数组（compare = equals）
	 * @param target		目标
	 * 
	 * @return 所在索引集（无序），空表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static <E extends Comparable<E>>List<Integer> binarySearchs2(E[] arr, E target){
		return binarySearchs2(arr, target, CommonComparator.get());
	}
	
	/**
	 * 二分（折半）查找 - 递归
	 * 
	 * @param arr			有序数组（compare = equals）
	 * @param target		目标
	 * @param left			左索引
	 * @param right			右索引
	 * @param comparator	比较器
	 * 
	 * @return 第1个查找到的索引，-1表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	private static <E>int binarySearch2(E[] arr, E target, int left, int right, Comparator<E> comparator){
		// 查找完成
		if (left > right) {
			return -1;
		}
		// 左侧比较
		int cp = comparator.compare(target, arr[left]);
		if (cp < 0) {
			// 目标 < 左侧
			return -1;
		}else if(cp == 0){
			// 目标 = 左侧
			return left;
		}
		// 右侧比较
		cp = comparator.compare(target, arr[right]);
		if (cp > 0) {
			// 右侧 < 目标
			return -1;
		}else if(cp == 0){
			// 右侧 = 目标
			return right;
		}
		// 折半切分
		int mid = (left + right) / 2;
		// 中点比较
		cp = comparator.compare(target, arr[mid]);
		if (cp > 0) {
			// 中点 < 目标 < 右侧 = 向右递归查找
			return binarySearch2(arr, target, mid + 1, right - 1, comparator);
		}else if (cp < 0) {
			// 左侧 < 目标 < 中点 = 向左递归查找
			return binarySearch2(arr, target, left + 1, mid - 1, comparator);
		}else {
			// 目标 = 中点
			return mid;
		}
	}
	
	/**
	 * 二分（折半）查找 - 递归
	 * 
	 * @param arr			有序数组（compare = equals）
	 * @param target		目标
	 * @param left			左索引
	 * @param right			右索引
	 * @param comparator	比较器
	 * @param indexs		索引存储器
	 * 
	 * @return 所在索引集（无序），空表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	private static <E>List<Integer> binarySearchs2(E[] arr, E target, int left, int right, Comparator<E> comparator, List<Integer> indexs){
		// 查找完成
		if (left > right) {
			return indexs;
		}
		// 左侧比较
		int cp = comparator.compare(target, arr[left]);
		if (cp < 0) {
			// 目标 < 左侧
			return indexs;
		}else if(cp == 0){
			// 目标 = 左侧
			indexs.add(left);
			// 扫描右侧
			right = arr.length - 1;
			while (true) {
				left++;
				if (left > right || comparator.compare(target, arr[left]) != 0) {
					break;
				}
				indexs.add(left);
			}
			return indexs;
		}
		// 右侧比较
		cp = comparator.compare(target, arr[right]);
		if (cp > 0) {
			// 右侧 < 目标
			return indexs;
		}else if(cp == 0){
			// 右侧 = 目标
			indexs.add(right);
			// 扫描左侧
			while (true) {
				right--;
				if (right < 0 || comparator.compare(target, arr[right]) != 0) {
					break;
				}
				indexs.add(right);
			}
			return indexs;
		}
		// 折半切分
		int mid = (left + right) / 2;
		// 中点比较
		cp = comparator.compare(target, arr[mid]);
		if (cp > 0) {
			// 中点 < 目标 < 右侧 = 向右递归查找
			return binarySearchs2(arr, target, mid + 1, right - 1, comparator, indexs);
		}else if (cp < 0) {
			// 左侧 < 目标 < 中点 = 向左递归查找
			return binarySearchs2(arr, target, left + 1, mid - 1, comparator, indexs);
		}else {
			// 目标 = 中点
			indexs.add(mid);
			// 扫描左侧
			right = mid;
			while (true) {
				right--;
				if (right < 0 || comparator.compare(target, arr[right]) != 0) {
					break;
				}
				indexs.add(right);
			}
			// 扫描右侧
			left = mid;
			right = arr.length - 1;
			while (true) {
				left++;
				if (left > right || comparator.compare(target, arr[left]) != 0) {
					break;
				}
				indexs.add(left);
			}
			return indexs;
		}
	}
	
	/**
	 * 插入查找
	 * 
	 * @param arr			均匀分布的有序数组（compare = equals）
	 * @param target		目标
	 * @param comparator	比较器
	 * @param calculator	计算器：将元素转换为整数，方便计算查询点
	 * 
	 * @return 第1个查找到的索引，-1表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static <E>int insertSearch(E[] arr, E target, Comparator<E> comparator, Function<E,Integer> calculator){
		// 数据校验
		if (arr == null || target == null || arr.length == 0) {
			return -1;
		}
		// 插入查找：对数据均匀分布的有序数组，自适应查询点来递归切分、查找
		return insertSearch(arr, target, 0, arr.length - 1, comparator, calculator);
	}
	
	/**
	 * 插入查找
	 * 
	 * @param arr			均匀分布的有序数组（compare = equals）
	 * @param target		目标
	 * @param calculator	计算器：将元素转换为整数，方便计算查询点
	 * 
	 * @return 第1个查找到的索引，-1表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static <E extends Comparable<E>>int insertSearch(E[] arr, E target, Function<E,Integer> calculator){
		return insertSearch(arr, target, CommonComparator.get(), calculator);
	}
	
	/**
	 * 插入查找
	 * 
	 * @param arr			均匀分布的有序数组（compare = equals）
	 * @param target		目标
	 * @param comparator	比较器
	 * @param calculator	计算器：将元素转换为整数，方便计算查询点
	 * 
	 * @return 所在索引集（无序），空表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static <E>List<Integer> insertSearchs(E[] arr, E target, Comparator<E> comparator, Function<E,Integer> calculator){
		// 索引存储器
		List<Integer> indexs = new ArrayList<>();
		// 数据校验
		if (arr == null || target == null || arr.length == 0) {
			return indexs;
		}		
		// 插入查找：对数据均匀分布的有序数组，自适应查询点来递归切分、查找
		return insertSearchs(arr, target, 0, arr.length -1 , comparator, calculator, indexs);
	}
	
	/**
	 * 插入查找
	 * 
	 * @param arr			均匀分布的有序数组（compare = equals）
	 * @param target		目标
	 * @param calculator	计算器：将元素转换为整数，方便计算查询点
	 * 
	 * @return 所在索引集（无序），空表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static <E extends Comparable<E>>List<Integer> insertSearchs(E[] arr, E target, Function<E,Integer> calculator){
		return insertSearchs(arr, target, CommonComparator.get(), calculator);
	}
	
	/**
	 * 插入查找
	 * 
	 * @param arr			均匀分布的有序数组（compare = equals）
	 * @param target		目标
	 * @param left			左索引
	 * @param right			右索引
	 * @param comparator	比较器
	 * @param calculator	计算器：将元素转换为整数，方便计算查询点
	 * 
	 * @return 第1个查找到的索引，-1表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	private static <E>int insertSearch(E[] arr, E target, int left, int right, Comparator<E> comparator, Function<E,Integer> calculator){
		// 查找完成
		if (left > right) {
			return -1;
		}
		// 左侧比较
		int cp = comparator.compare(target, arr[left]);
		if (cp < 0) {
			// 目标 < 左侧
			return -1;
		}else if(cp == 0){
			// 目标 = 左侧
			return left;
		}
		// 右侧比较
		cp = comparator.compare(target, arr[right]);
		if (cp > 0) {
			// 右侧 < 目标
			return -1;
		}else if(cp == 0){
			// 右侧 = 目标
			return right;
		}
		// 自适应切分
		int mid = left + (right - left) * (calculator.apply(target) - calculator.apply(arr[left])) / (calculator.apply(arr[right]) - calculator.apply(arr[left]));
		// 中点比较
		cp = comparator.compare(target, arr[mid]);
		if (cp > 0) {
			// 中点 < 目标 < 右侧 = 向右递归查找
			return insertSearch(arr, target, mid + 1, right - 1, comparator, calculator);
		}else if (cp < 0) {
			// 左侧 < 目标 < 中点 = 向左递归查找
			return insertSearch(arr, target, left + 1, mid - 1, comparator, calculator);
		}else {
			// 目标 = 中点
			return mid;
		}
	}
	
	/**
	 * 插入查找
	 * 
	 * @param arr			均匀分布的有序数组（compare = equals）
	 * @param target		目标
	 * @param left			左索引
	 * @param right			右索引
	 * @param comparator	比较器
	 * @param calculator	计算器：将元素转换为整数，方便计算查询点
	 * @param indexs		索引存储器
	 * 
	 * @return 所在索引集（无序），空表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	private static <E>List<Integer> insertSearchs(E[] arr, E target, int left, int right, Comparator<E> comparator, Function<E,Integer> calculator, List<Integer> indexs){
		// 查找完成
		if (left > right) {
			return indexs;
		}
		// 左侧比较
		int cp = comparator.compare(target, arr[left]);
		if (cp < 0) {
			// 目标 < 左侧
			return indexs;
		}else if(cp == 0){
			// 目标 = 左侧
			indexs.add(left);
			// 扫描右侧
			right = arr.length - 1;
			while (true) {
				left++;
				if (left > right || comparator.compare(target, arr[left]) != 0) {
					break;
				}
				indexs.add(left);
			}
			return indexs;
		}
		// 右侧比较
		cp = comparator.compare(target, arr[right]);
		if (cp > 0) {
			// 右侧 < 目标
			return indexs;
		}else if(cp == 0){
			// 右侧 = 目标
			indexs.add(right);
			// 扫描左侧
			while (true) {
				right--;
				if (right < 0 || comparator.compare(arr[right], target) != 0) {
					break;
				}
				indexs.add(right);
			}
			return indexs;
		}
		// 自适应切分
		int mid = left + (right - left) * (calculator.apply(target) - calculator.apply(arr[left])) / (calculator.apply(arr[right]) - calculator.apply(arr[left]));
		// 中点比较
		cp = comparator.compare(target, arr[mid]);
		if (cp > 0) {
			// 中点 < 目标 < 右侧 = 向右递归查找
			return insertSearchs(arr, target, mid + 1, right - 1, comparator, calculator, indexs);
		}else if (cp < 0) {
			// 左侧 < 目标 < 中点 = 向左递归查找
			return insertSearchs(arr, target, left + 1, mid - 1, comparator, calculator, indexs);
		}else {
			// 目标 = 中点
			indexs.add(mid);
			// 扫描左侧
			right = mid;
			while (true) {
				right--;
				if (right < 0 || comparator.compare(target, arr[right]) != 0) {
					break;
				}
				indexs.add(right);
			}
			// 扫描右侧
			left = mid;
			right = arr.length - 1;
			while (true) {
				left++;
				if (left > right || comparator.compare(target, arr[left]) != 0) {
					break;
				}
				indexs.add(left);
			}
			return indexs;
		}
	}
	
	/**
	 * 斐波那契（黄金分割）查找
	 * 
	 * @param arr			有序数组（compare = equals）
	 * @param target		目标
	 * @param comparator	比较器
	 * 
	 * @return 第1个查找到的索引，-1表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static <E>int fibonacciSearch(E[] arr, E target, Comparator<E> comparator){
		// 数据校验
		if (arr == null || target == null || arr.length == 0) {
			return -1;
		}
		// 数组区间
		int left = 0;
		int right = arr.length -1;
		// 切分点
		int mid;
		// 斐波那契数列
		List<Integer> fs = new ArrayList<>();
		fs.add(1);
		fs.add(1);
		fs.add(2);
		// 斐波那契数索引
		int k = 2;
		// 获取与数组长度最接近的斐波那契数
		while(arr.length > fs.get(k) -1) {
			// 添加斐波那契数：F[k] = F[k-1] + F[k-2]
			k++;
			fs.add(fs.get(k-1) + fs.get(k-2));
		}
		// 增长数组，使其长度等于斐波那契数
		E[] tmp = Arrays.copyOf(arr, fs.get(k));
		for (int i = arr.length; i < tmp.length; i++) {
			tmp[i] = arr[right];
		}
		
		// 斐波那契查找：根据斐波那契数列，将有序数组以黄金比例分割、查找
		int cp;
		while (left <= right) {
			// 黄金分割
			mid = left + fs.get(k-1) - 1;
			// 中点比较
			cp = comparator.compare(target, tmp[mid]);
			if (cp < 0) {
				// 目标 < 中点 = 向左查找
				right = mid -1;
				// F[k] = F[k-1] + F[k-2] >> F[k-1]
				k--;
			} else if(cp > 0){
				// 中点 < 目标 = 向右查找
				left = mid + 1;
				// F[k] = F[k-1] + F[k-2] >> F[k-2]
				k -=2;
			}else {
				// 目标 = 中点/数组的增长部分
				return Math.min(mid, right);
			}
		}
		return -1;
	}
	
	/**
	 * 斐波那契（黄金分割）查找
	 * 
	 * @param arr			有序数组（compare = equals）
	 * @param target		目标
	 * 
	 * @return 第1个查找到的索引，-1表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static <E extends Comparable<E>>int fibonacciSearch(E[] arr, E target){
		return fibonacciSearch(arr, target, CommonComparator.get());
	}
	
	/**
	 * 斐波那契（黄金分割）查找
	 * 
	 * @param arr			有序数组（compare = equals）
	 * @param target		目标
	 * @param comparator	比较器
	 * 
	 * @return 第1个查找到的索引，-1表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static <E>List<Integer> fibonacciSearchs(E[] arr, E target, Comparator<E> comparator){
		// 索引存储器
		List<Integer> indexs = new ArrayList<>();
		// 数据校验
		if (arr == null || target == null || arr.length == 0) {
			return indexs;
		}	
		// 数组区间
		int left = 0;
		int right = arr.length -1;
		// 切分点
		int mid;
		// 斐波那契数列
		List<Integer> fs = new ArrayList<>();
		fs.add(1);
		fs.add(1);
		fs.add(2);
		// 斐波那契数索引
		int k = 2;
		// 获取与数组长度最接近的斐波那契数
		while(arr.length > fs.get(k) -1) {
			// 添加斐波那契数：F[k] = F[k-1] + F[k-2]
			k++;
			fs.add(fs.get(k-1) + fs.get(k-2));
		}
		// 增长数组，使其长度等于斐波那契数
		E[] tmp = Arrays.copyOf(arr, fs.get(k));
		for (int i = arr.length; i < tmp.length; i++) {
			tmp[i] = arr[right];
		}
		
		// 斐波那契查找：根据斐波那契数列，将有序数组以黄金比例分割、查找
		int cp;
		while (left <= right) {
			// 黄金分割
			mid = left + fs.get(k-1) - 1;
			// 中点比较
			cp = comparator.compare(target, tmp[mid]);
			if (cp < 0) {
				// 目标 < 中点 = 向左查找
				right = mid -1;
				// F[k] = F[k-1] + F[k-2] >> F[k-1]
				k--;
			} else if(cp > 0){
				// 中点 < 目标 = 向右查找
				left = mid + 1;
				// F[k] = F[k-1] + F[k-2] >> F[k-2]
				k -=2;
			}else {
				// 目标 = 中点
				if (mid > right) {
					// 数组的增长部分
					mid = right;
				}
				indexs.add(mid);
				// 扫描左侧
				right = mid;
				while (true) {
					right--;
					if (right < 0 || comparator.compare(target, arr[right]) != 0) {
						break;
					}
					indexs.add(right);
				}
				// 扫描右侧
				left = mid;
				right = arr.length - 1;
				while (true) {
					left++;
					if (left > right || comparator.compare(target, arr[left]) != 0) {
						break;
					}
					indexs.add(left);
				}
			}
		}
		return indexs;
	}
	
	/**
	 * 斐波那契（黄金分割）查找
	 * 
	 * @param arr			有序数组（compare = equals）
	 * @param target		目标
	 * 
	 * @return 第1个查找到的索引，-1表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月15日
	 */
	public static <E extends Comparable<E>>List<Integer> fibonacciSearchs(E[] arr, E target){
		return fibonacciSearchs(arr, target, CommonComparator.get());
	}
	
	/**
	 * 背包问题（动态规划算法）
	 * 
	 * @param w		物品重量
	 * @param v		物品价值
	 * @param max 	背包容量（重量）
	 * 
	 * @return [入包物品]
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月27日
	 */
	public static List<Integer> knapsack(int[] w, int[] v, int max) {
		// 建表：物品 * 背包（划分为0~max容量的多个背包）的最大价值
		int[][] table = new int[v.length][max + 1];
		for (int i = 0; i < table.length; i++) {
			// 容量为空：不能放入，价值为0
			table[i][0] = 0;
		}

		// 填表：依次放入物品，到不同容量的背包
		int sum;
		boolean[][] log = new boolean[table.length][table[0].length];
		for (int i = 0; i < table.length; i++) {
			for (int j = 1; j < table[0].length; j++) {
				if (j < w[i]) {
					// 容量不足：放入上个物品
					table[i][j] = i == 0 ? 0 : table[i-1][j];
				}else {
					// 容量充足
					if (i == 0) {
						// 第一个物品：直接放入
						table[i][j] = v[i];
						log[i][j] = true;
					}else {
						// 拆分为两个背包：物品 + 上个物品[剩余容量]
						sum = v[i] + table[i-1][j-w[i]];
						if (table[i-1][j] > sum) {
							// 两个背包价值小于上个物品：放入上个物品
							table[i][j] =  table[i-1][j];
						}else {
							// 放入物品
							table[i][j] = sum;
							log[i][j] = true;
						}
					}
				}
			}
		}
		
		// 读取最终放入记录（逆推填表过程）
		List<Integer> result = new ArrayList<>();
		int i = log.length-1;
		int j = log[0].length-1;
		while(i >= 0 && j > 0) {
			if (log[i][j]) {
				// 放入物品
				result.add(i);
				// 拆包
				j -= w[i];
			}
			// 上个物品
			i--;
		}
		return result;
	}
	
}
